iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 29
0
自我挑戰組

LeetCode演算法刷題 使用Go系列 第 29

Day29-[LeetCode演算法刷題 使用Go] -Move Zeroes

  • 分享至 

  • xImage
  •  

題目連結: Move Zeroes

題目描述為: 給定一組陣列,我們需要將所有的 0 元素移到陣列最後面,且不更動原本順序。題目有補充說明,希望我們採用 in-place的方式來完成。

例子 1: input=[0,1,0,3,12], output=[1,3,12,0,0]。

思路 1: 創建新陣列

我們可以創建一個新的陣列,大小與原本的一致,依序儲存非 0 元素,最後剩下的位置皆為 0 元素,再將原陣列按照此順序賦值。

  • 複雜度評估
    設陣列大小為 N ,我們需要遍歷該陣列兩次,時間複雜度為 O(N)。
    此方法需要創建一個大小為 N 的陣列,空間複雜度為 O(N)。

參考程式碼

func moveZeroes(nums []int)  {
    
    tmp:=make([]int,len(nums))
    idx:=0
              
    for _,v:=range nums{
        
        if v==0{
            continue
        }
                  
        tmp[idx]=v
        idx++   
    }
    
    for i,_:=range nums{
        nums[i]=tmp[i]
    }
    
}

思路 2: 類泡沫排序法

我們可以仿造泡沫排序法的方式,將元素兩兩比較,若前者元素值為 0,則交換位置。

  • 複雜度評估
    設陣列大小為 N,泡沫排序法時間複雜度為 O(N²)。
    此方法滿足 in-place,空間複雜度為 O(1)。

參考程式碼

func moveZeroes(nums []int)  {
    
    for i:=0;i<len(nums)-1;i++{
        for j:=i+1;j<len(nums);j++{
            if nums[i]==0{
                nums[i],nums[j]=nums[j],nums[i]
            }
        }
    }
    
}

思路 3: 原地寫入法

我們可以用一個變數 j 初始化為 0,用來紀錄當前寫入的index,直接遍歷整個陣列,當元素不為 0 時,直接擺到 index=j 的位置。當遍歷完後再將 j 當下位置後面的元素皆設為 0。

  • 複雜度評估
    設陣列大小為 N,此方法至多需要遍歷該陣列兩次,時間複雜度為 O(N)。
    此方法滿足 in-place,空間複雜度為 O(1)。

參考程式碼

func moveZeroes(nums []int)  {
    
    j:=0 
    for i:=0;i<len(nums);i++{
        if nums[i]!=0{
            nums[j]=nums[i]
            j++
        }        
    }
    
    for j<len(nums){
        nums[j]=0
        j++
    }
}

小結:

方法 1 需要額外的記憶體空間,不滿足 in-place 原則。
方法 2 仿造了泡沫排序法的形式,時間複雜度較高。
方法 3 滿足 in-place 原則,且時間複雜度較低,為此題的理想解法。
我將解法加上簡單的測試,附上程式碼到此。

補充:

當有 N 個元素需要排序時,我們一般認定對它排序的時間複雜度為 O(NlogN)。
而 in-place 原則讓我們注意對記憶體空間的管理。在過去的時代,記憶體空間極少但仍舊完成了登月任務


上一篇
Day28-[LeetCode演算法刷題 使用Go] -Majority Element
下一篇
Day30-[LeetCode演算法刷題 使用Go] -Perfect Number
系列文
LeetCode演算法刷題 使用Go30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言